Recursive versus sequential multiple error measures reduction: a curve simplification approach to ECG data compression.
Identifieur interne : 000026 ( Main/Exploration ); précédent : 000025; suivant : 000027Recursive versus sequential multiple error measures reduction: a curve simplification approach to ECG data compression.
Auteurs : Bachir Boucheham [Algérie] ; Youcef Ferdi ; Mohamed Chawki BatoucheSource :
- Computer methods and programs in biomedicine [ 0169-2607 ] ; 2006.
Descripteurs français
- KwdFr :
- MESH :
- méthodes : Compression de données.
- statistiques et données numériques : Compression de données.
- Algorithmes, Interprétation statistique de données, Électrocardiographie.
English descriptors
- KwdEn :
- MESH :
- methods : Data Compression.
- statistics & numerical data : Data Compression.
- Algorithms, Data Interpretation, Statistical, Electrocardiography.
Abstract
Previous time domain compression methods have been tackled by sequential one point at a time sub-optimal selection strategies running in approximately O(N) or all points at a time optimal strategies running in approximately O(N3) temporal complexities. Yet basically, the selected dominant points (DPs) are locally only significant in these methods, which may lead to inaccurate reconstruction or even loss of clinical data. Alternatively, the recursive one point at a time selection strategy, through different variants of the Douglas-Peucker line simplification algorithm, computes globally significant DPs for an approximately O(N.log2(N)) temporal complexity. We illustrate that the recursive strategy performs numerically almost two times better than the sequential one. The piecewise linear approximation of the input ECG is formally expressed as a curve simplification problem, through reduction of the Hausdorff error measure. We also illustrate that reduction of two error measures performs better than reduction of one error measure. An additional compression option is proposed in the case of the recursive strategy through simplification of the sorted distances associated to the selected set of points. The outcome is a compression algorithm that yields compression ratios ranging from 8:1 to 22:1 for a perceptually good reconstruction quality and near linear execution time. The tests have been conducted on the MIT-BIH public ECG database. Results show that the proposed recursive algorithm is an excellent compromise on compression ratio - computational time - reconstruction quality.
DOI: 10.1016/j.cmpb.2005.11.008
PubMed: 16413633
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream PubMed, to step Corpus: 000799
- to stream PubMed, to step Curation: 000795
- to stream PubMed, to step Checkpoint: 000792
- to stream Main, to step Merge: 000026
- to stream Main, to step Curation: 000026
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Recursive versus sequential multiple error measures reduction: a curve simplification approach to ECG data compression.</title><author><name sortKey="Boucheham, Bachir" sort="Boucheham, Bachir" uniqKey="Boucheham B" first="Bachir" last="Boucheham">Bachir Boucheham</name><affiliation wicri:level="1"><nlm:affiliation>Department of Computer Science, University of Skikda, Algeria, BP 26, Route El-Hadaik, Skikda DZ21000, Algeria. boucheham_bachir@yahoo.fr</nlm:affiliation><country xml:lang="fr">Algérie</country><wicri:regionArea>Department of Computer Science, University of Skikda, Algeria, BP 26, Route El-Hadaik, Skikda DZ21000</wicri:regionArea><wicri:noRegion>Skikda DZ21000</wicri:noRegion></affiliation></author><author><name sortKey="Ferdi, Youcef" sort="Ferdi, Youcef" uniqKey="Ferdi Y" first="Youcef" last="Ferdi">Youcef Ferdi</name></author><author><name sortKey="Batouche, Mohamed Chawki" sort="Batouche, Mohamed Chawki" uniqKey="Batouche M" first="Mohamed Chawki" last="Batouche">Mohamed Chawki Batouche</name></author></titleStmt><publicationStmt><idno type="wicri:source">PubMed</idno><date when="2006">2006</date><idno type="RBID">pubmed:16413633</idno><idno type="pmid">16413633</idno><idno type="doi">10.1016/j.cmpb.2005.11.008</idno><idno type="wicri:Area/PubMed/Corpus">000799</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">000799</idno><idno type="wicri:Area/PubMed/Curation">000795</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">000795</idno><idno type="wicri:Area/PubMed/Checkpoint">000792</idno><idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">000792</idno><idno type="wicri:Area/Main/Merge">000026</idno><idno type="wicri:Area/Main/Curation">000026</idno><idno type="wicri:Area/Main/Exploration">000026</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Recursive versus sequential multiple error measures reduction: a curve simplification approach to ECG data compression.</title><author><name sortKey="Boucheham, Bachir" sort="Boucheham, Bachir" uniqKey="Boucheham B" first="Bachir" last="Boucheham">Bachir Boucheham</name><affiliation wicri:level="1"><nlm:affiliation>Department of Computer Science, University of Skikda, Algeria, BP 26, Route El-Hadaik, Skikda DZ21000, Algeria. boucheham_bachir@yahoo.fr</nlm:affiliation><country xml:lang="fr">Algérie</country><wicri:regionArea>Department of Computer Science, University of Skikda, Algeria, BP 26, Route El-Hadaik, Skikda DZ21000</wicri:regionArea><wicri:noRegion>Skikda DZ21000</wicri:noRegion></affiliation></author><author><name sortKey="Ferdi, Youcef" sort="Ferdi, Youcef" uniqKey="Ferdi Y" first="Youcef" last="Ferdi">Youcef Ferdi</name></author><author><name sortKey="Batouche, Mohamed Chawki" sort="Batouche, Mohamed Chawki" uniqKey="Batouche M" first="Mohamed Chawki" last="Batouche">Mohamed Chawki Batouche</name></author></analytic><series><title level="j">Computer methods and programs in biomedicine</title><idno type="ISSN">0169-2607</idno><imprint><date when="2006" type="published">2006</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms (MeSH)</term><term>Data Compression (methods)</term><term>Data Compression (statistics & numerical data)</term><term>Data Interpretation, Statistical (MeSH)</term><term>Electrocardiography (MeSH)</term></keywords><keywords scheme="KwdFr" xml:lang="fr"><term>Algorithmes (MeSH)</term><term>Compression de données (méthodes)</term><term>Compression de données (statistiques et données numériques)</term><term>Interprétation statistique de données (MeSH)</term><term>Électrocardiographie (MeSH)</term></keywords><keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Data Compression</term></keywords><keywords scheme="MESH" qualifier="méthodes" xml:lang="fr"><term>Compression de données</term></keywords><keywords scheme="MESH" qualifier="statistics & numerical data" xml:lang="en"><term>Data Compression</term></keywords><keywords scheme="MESH" qualifier="statistiques et données numériques" xml:lang="fr"><term>Compression de données</term></keywords><keywords scheme="MESH" xml:lang="en"><term>Algorithms</term><term>Data Interpretation, Statistical</term><term>Electrocardiography</term></keywords><keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term><term>Interprétation statistique de données</term><term>Électrocardiographie</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Previous time domain compression methods have been tackled by sequential one point at a time sub-optimal selection strategies running in approximately O(N) or all points at a time optimal strategies running in approximately O(N3) temporal complexities. Yet basically, the selected dominant points (DPs) are locally only significant in these methods, which may lead to inaccurate reconstruction or even loss of clinical data. Alternatively, the recursive one point at a time selection strategy, through different variants of the Douglas-Peucker line simplification algorithm, computes globally significant DPs for an approximately O(N.log2(N)) temporal complexity. We illustrate that the recursive strategy performs numerically almost two times better than the sequential one. The piecewise linear approximation of the input ECG is formally expressed as a curve simplification problem, through reduction of the Hausdorff error measure. We also illustrate that reduction of two error measures performs better than reduction of one error measure. An additional compression option is proposed in the case of the recursive strategy through simplification of the sorted distances associated to the selected set of points. The outcome is a compression algorithm that yields compression ratios ranging from 8:1 to 22:1 for a perceptually good reconstruction quality and near linear execution time. The tests have been conducted on the MIT-BIH public ECG database. Results show that the proposed recursive algorithm is an excellent compromise on compression ratio - computational time - reconstruction quality.</div></front></TEI><affiliations><list><country><li>Algérie</li></country></list><tree><noCountry><name sortKey="Batouche, Mohamed Chawki" sort="Batouche, Mohamed Chawki" uniqKey="Batouche M" first="Mohamed Chawki" last="Batouche">Mohamed Chawki Batouche</name><name sortKey="Ferdi, Youcef" sort="Ferdi, Youcef" uniqKey="Ferdi Y" first="Youcef" last="Ferdi">Youcef Ferdi</name></noCountry><country name="Algérie"><noRegion><name sortKey="Boucheham, Bachir" sort="Boucheham, Bachir" uniqKey="Boucheham B" first="Bachir" last="Boucheham">Bachir Boucheham</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Sante/explor/MaghrebDataLibMedV2/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000026 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000026 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Sante
|area= MaghrebDataLibMedV2
|flux= Main
|étape= Exploration
|type= RBID
|clé= pubmed:16413633
|texte= Recursive versus sequential multiple error measures reduction: a curve simplification approach to ECG data compression.
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Main/Exploration/RBID.i -Sk "pubmed:16413633" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd \
| NlmPubMed2Wicri -a MaghrebDataLibMedV2
| This area was generated with Dilib version V0.6.38. |  |